﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_140 : BaseProblem
    {
        public override object GetResult()
        {
            const int index = 30;

            var hs = new List<long>();

            ulong sum = 0;

            long mx = long.MaxValue/10;

            var rs = new List<long>();
            Forme(ref hs, mx, 8, -2);
            rs.AddRange(hs);
            hs.Clear();

            Forme(ref hs, mx, 7, 1);
            rs.AddRange(hs);
            hs.Clear();

            Forme(ref hs, mx, 17, 7);
            rs.AddRange(hs);
            hs.Clear();

            rs.Sort();

            var lst = new List<long>();
            foreach (var r in rs)
            {
                if (r <= 12)
                    continue;
                if ((r - 7)%5 != 0) continue;
                lst.Add((r - 7) / 5);
                sum += (ulong)lst[lst.Count - 1];
                if (lst.Count == index)
                    return sum;
            }
            return sum;
        }

        private static void Forme(ref List<long> result, long max, long x, long y)
        {
            if (x > max || x < -max)
                return;
            if (result.Contains(x))
                return;
            result.Add(x);
            Forme(ref result, max, x * 9 + 20 * y, x * 4 + 9 * y);
            Forme(ref result, max, x * 9 - 20 * y, x * 4 - 9 * y);
        }

        public override string Problem
        {
            get
            {
                return @"Consider the infinite polynomial series AG(x) = xG1 + x2G2 + x3G3 + ..., where Gk is the kth term of the second order recurrence relation Gk = Gk1 + Gk2, G1 = 1 and G2 = 4; that is, 1, 4, 5, 9, 14, 23, ... .

For this problem we shall be concerned with values of x for which AG(x) is a positive integer.

The corresponding values of x for the first five natural numbers are shown below.

x	AG(x)
(51)/4	1
2/5	2
(222)/6	3
(1375)/14	4
1/2	5
We shall call AG(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 20th golden nugget is 211345365.

Find the sum of the first thirty golden nuggets.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 5673835352990;
            }
        }

    }
}
